package j2024.j202412;

import java.util.ArrayList;
import java.util.List;

public class j1214 {
    /**
     * 54. 螺旋矩阵
     * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0,right = n-1,top = 0,bottom = m-1;
        List<Integer> ret = new ArrayList<>();
        while(true){
            for (int i = left; i <= right; i++) {
                ret.add(matrix[top][i]);
            }
            if(++top>bottom)  break;
            for (int i = top; i <= bottom; i++) {
                ret.add(matrix[i][right]);
            }
            if(--right<left) break;
            for (int i = right; i >= left; i--) {
                ret.add(matrix[bottom][i]);
            }
            if(--bottom<top) break;
            for (int i = bottom; i >= top; i--) {
                ret.add(matrix[i][left]);
            }
            if(++left>right) break;
        }
        return ret;
    }

    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> ret = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ret;
        }
        int rows = matrix.length, cols = matrix[0].length;
        boolean[][] vis = new boolean[rows][cols];
        int total = rows * cols;
        int row = 0, col = 0;
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dirI = 0;
        for (int i = 0; i < total; i++) {
            ret.add(matrix[row][col]);
            vis[row][col] = true;
            int nextRow = row + dir[dirI][0], nextCol = col + dir[dirI][1];
            //判断是否需要调转方向
            if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols || vis[nextRow][nextCol]) {
                dirI = (dirI + 1) % 4;
            }
            row += dir[dirI][0];
            col += dir[dirI][1];
        }
        return ret;
    }


}
